\documentclass[11pt,a4paper]{report}

\usepackage[french]{babel}
\usepackage[utf8]{inputenc}
\usepackage{graphicx}
\usepackage{makeidx}


\title{\emph{Rapport de Projet d'Intelligence Artificielle}\\Jeu du Morpion 15x15 avec un alignement de 5}

\author{Francois \textsc{HUVE}\\Murat \textsc{ALTUNTAS}}


\begin{document}


\maketitle

\tableofcontents

\chapter{Introduction}
Dans le cadre de notre module d'intelligence artificielle nous avons été amenés à programmer le jeu du Morpion 15x15 avec un alignement de 5 pour gagner, dans le but ensuite de pouvoir y intégrer un algorithme d'intelligence artificielle pour tester nos connaissances et nos compétences dans le domaine.

Dans ce rapport nous présenterons donc des informations permettant de mieux comprendre nos différentes initiatives dans le cadre de ce projet.

\chapter{Analyse du jeu}
Avant de pouvoir commencer à programmer une IA ou même le jeu en lui même nous avons en premier lieu cherché à déterminer une représentation du jeu qui nous permettrait ensuite de réaliser tous les algorithmes nécessaire. Il nous est donc apparu qu'il nous fallait stocker les informations des 225 cases que constitue le plateau de jeu. Les informations concernant une case étant si la case était vide ou alors si un des deux joueur avait posé un pion à cet emplacement. Une des autres informations que l'on devait être en mesure de garder en mémoire était le tour de jeu. En effet étant un jeu à deux joueurs il nous fallait à tout moment être en mesure de savoir qui devait jouer.

Après avoir défini l'environnement il nous fallait définir les méthodes de jeu. Ainsi comme l'unique chose que l'on fait pour jouer ce jeu est de poser un pion dans une case si elle n'est pas déjà occupée cette partie fût relativement simple à mettre en œuvre.

Une fois les actions et l'environnement défini il nous fallait alors être en mesure de détecter la fin d'une partie. Une victoire est annoncée quand l'un des deux joueurs effectue un alignement de 5 pions ou plus en ligne, en colonne ou en diagonale. 

\chapter{l'IA}
\section{Choix du type d'IA}
Une fois que le code permettant de jouer contre un autre humain fût opérationnel nous avons consacré notre temps au codage de l'IA du jeu. Mais avant toute de chose il nous fallait déterminer le genre d'algorithme qu'il nous fallait implémenter. Comme le jeu du morpion et un jeu dans lequel l'univers est entièrement connu et qu'il nécessite deux joueur, un algorithme de jeu nous a paru le plus approprié. Parmi les diffèrents choix d'algorithmes de jeux que nous connaissons nous avons choisi l'Alpha-Beta avec un convention NegaMax.

Les raisons de ce choix sont que comme lors d'un tour on peut poser son pion n'importe où sur le plateau et de même le coup suivant l'arbre de développement des algorithmes de recherche deviennent vite lent. Or l'Alpha-Beta permet un élagage important au niveau de l'arbre de recherche ce qui nous a incité à le choisir. Le fait de choisir la convention NegaMax n'est quand elle justifiée que par le fait qu'elle permet une certaine simplification du code en empêchant l'écriture de deux fonctions presque similaires utilisées dans le cas de la convention MinMax.

\section{heuristique}
L'heuristique donne au plateau une valeur, en fonction du joueur courant et du contenu du plateau, peu importe l'ordre dans lequel les évènements ont eu lieu. Pour notre heuristique, nous avons donc choisi de parcourir la totalité du plateau, en récupérant pour chaque case une valeur : dans chaque axe passant par ce point courant, nous avons compté les pions de même couleur atteignables depuis le centre du segment, et nous avons forcé cette valeur à 0 si on ne pouvait pas visiter ce segment de 5 cases en entier pour cause de limite de plateau ou de pion adverse. Cette valeur a également été fixée à 10 pour un alignement de 4 pions de la couelur courant analysée, et à 20 pour 5 pions. Cette partie de l'algorithle donnait donc pour chaque axe de chaque pion le nombre de pions alignables de la même couleur, et 0 s'il n'y avait pas assez de place pour y faire un alignement complet, ceci piur éviter plus tard à L'IA de considérer cette case comme utile sur le chemin vers la victoire. Ensuite, toujours pour chaque pion, les valeurs de chacun de ces axes ont été passés en exposant du chiffre 3, puis additionnés entres eux. Ceci pour obtenir une valeur favorisant les alignements aux "tas" qu'aurait pu former l'IA. Ensuite, ce petit algorithme est effectué pour toutes les cases, et les valeurs sont additionnées. Ceci donnt la valeur du plateau pour une couleur de joueur. Ensuite la même opération est effectuée pour les pions de l'autre couleur ( donc l'ennemi ) puis ce résultat est soustrait au premier. Ce qui donne une valeur négative pour un plateau défavorable à l'état courant, une valeur nulle pour un plateau équilibré entre les 2 concurrents, et une valeur positive lorsque le plateau est bon pour le joueur appelant cet algorithme (le joueur initial dans l'arbre des coups initié au n-ieme coup). Une amélioration de cet algorithme permettait de renforcer ou d'affaiblir ces valeurs à l'aide de coeficients. Ceci allait un peu à l'encontre d'une heuristique d'un jeu à gain constant, mais elle permettait d'affiner le comportemt de l'IA en fonction de l'adversaire. Par exemple ilv aut mieux jouer plus défensif contre un humain que contre une autre IA pour éviter les pièges non détectés.
Malheureusement seules les profondeurs 2 et 3 étaient raisonnablement accessibles, et la profondeur 3 créait des réactions souvent imprévues du fait que l'IA appelle une heuristique avec un pion ennemi de plus, placé au mieux selon elle. Nous avons donc préféré jouer en profondeur 2 pendant le tournoi, et nous avons perdu contre une IA de profondeur 3. Malheureusement cette IA est deterministe, et pour l'indéterminiser il aurait fallu analyser la liste des coups possibles dans l'algorithme alpha beta de façon aléatoire. Globalement cette heuristique est quand même très satisfaisante.
\end{document}